package com.cdream.basic.algorithm.leetcode.bfs;

import java.util.*;

/**
 * @author cdream
 * @date 6/25/21
 */
public class Question752 {
    private Set<String> deadLock;
    public int openLock(String[] deadends, String target) {
        if ("0000".equals(target)) {
            return 0;
        }
        deadLock = new HashSet<>(Arrays.asList(deadends));
        if (deadLock.contains("0000")) {
            return -1;
        }
        Set<String> used = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.offer("0000");
        used.add("0000");
        int res = 0;
        while (!queue.isEmpty()){
            res++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String poll = queue.poll();
                List<String> strings = allPossible(poll);
                for (String string : strings) {
                    if (used.contains(string)||deadLock.contains(string)){
                        continue;
                    }
                    if (Objects.equals(string, target)){
                        return res;
                    }
                    queue.offer(string);
                    used.add(string);
                }
            }
        }
        return -1;
    }

    char next(char c) {
        return c == '9' ? '0' : (char) (c + 1);
    }

    char last(char c) {
        return c == '0' ? '9' : (char) (c - 1);
    }

    List<String> allPossible(String i) {
        ArrayList<String> res = new ArrayList<>();
        char[] chars = i.toCharArray();
        for (int j = 0; j < 4; j++) {
            char num = chars[j];
            char next = next(num);
            chars[j] = next;
            res.add(new String(chars));
            chars[j] = last(num);
            res.add(new String(chars));
            chars[j] = num;
        }
        return res;
    }
}
